/*
*	Author: Shyam (shyam2347@gmail.com)
*	March 26, 2012
*	This file will contain functions of cache
*/
#include <string.h>
#include <time.h>

struct _cacheset
{
	int index;
	struct cache_db *cdb;
};
typedef struct _cacheset cacheset;
void *l1icache, *l1dcache, *l2cache;
cacheset *l1icache_start, *l1dcache_start, *l2cache_start;

struct cache_db
{
	char tag[64];
	int val;
	struct cache_db *next;
};
typedef struct cache_db cachedb;

struct _tlb
{
	char tag[70];
	int val;
	struct _tlb *next;
	struct _tlb *prev;
};
typedef struct _tlb tlb;
tlb *itlb,*first_itlb, *dtlb, *first_dtlb;
void init_cache()
{
	first_itlb 	= NULL;
	itlb 		= NULL;
	first_dtlb 	= NULL;
	dtlb 		= NULL;
	l1icache 	= malloc(sizeof(struct _cacheset) * NO_OF_SETS_L1_I);
	l1icache_start  = l1icache;
	int i;
	cacheset *temp;
	for (i=0; i<NO_OF_SETS_L1_I; i++)
	{
		temp = (struct _cacheset *) l1icache;
		temp->cdb = NULL;
		l1icache += sizeof(struct _cacheset);
	}
	l1dcache 	= malloc(sizeof(struct _cacheset) * NO_OF_SETS_L1_D);
	l1dcache_start  = l1dcache;
	for (i=0; i<NO_OF_SETS_L1_D; i++)
	{
		temp = (struct _cacheset *) l1dcache;
		temp->cdb = NULL;
		l1dcache += sizeof(struct _cacheset);
	}

	l2cache 	= malloc(NO_OF_SETS_L2*sizeof(struct _cacheset));
	l2cache_start 	= l2cache;
	for (i=0; i<NO_OF_SETS_L2; i++)
	{
		temp = (struct _cacheset *) l2cache;
		temp->cdb = NULL;
		l2cache += sizeof(struct _cacheset);
	}
}

//TLB Functions
//Search - TLB entry if present, else return NULL
// i = 1 - iTLB, 2 - dTLB
tlb* tlb_search(char *address, int i)
{
	tlb *my_tlb;
	if (i == TLB_INSTR) my_tlb = first_itlb;
	else my_tlb = first_dtlb;
	if (my_tlb != NULL)
	{
		while (my_tlb != NULL)
		{
			if (strcmp(address, my_tlb->tag) == 0)
				break;
			my_tlb = my_tlb->next;
		}
	}
	return my_tlb;
}

//access -1 not present, 1 - present
int tlb_access(char *address, int i)
{
	tlb *temp = tlb_search(address, i);
	if (temp != NULL)
	{
		if (i == TLB_INSTR)
		{
			I_TLB_VAL = ++I_TLB_VAL%TLB_MAGICNO;
			temp->val = I_TLB_VAL;
		}
		else 
		{
			D_TLB_VAL = ++D_TLB_VAL%TLB_MAGICNO;
			temp->val = D_TLB_VAL;
		}
		return 1;
	}
	else
		return -1;
}

int diff(int m, int n)
{
	int diff = n - m;
	if (diff < 0)
	{
		diff = TLB_MAGICNO-m;
		diff += n;
	}
	return diff;
}

void tlb_miss (char *address, int i)
{
	tlb *my_tlb;
	if (i == TLB_INSTR) 
	{
		my_tlb = first_itlb;
		I_TLB_VAL = ++I_TLB_VAL%TLB_MAGICNO;
	}
	else 
	{
		my_tlb = first_dtlb;
		D_TLB_VAL = ++D_TLB_VAL%TLB_MAGICNO;
	}
	if (my_tlb != NULL && I_TLB_COUNT == I_TLB_SIZE && i == TLB_INSTR) // need to evict one and add the new one - I will just do replace
	{
		unsigned int t;
		int max = 0, tmp;
		if (i == TLB_INSTR) t = I_TLB_VAL;
		else t = D_TLB_VAL;
		tlb *temp = my_tlb;
		while (my_tlb != NULL)
		{
			tmp = diff(my_tlb->val,t);
			if (tmp > max )
			{
				temp = my_tlb;
				max = tmp;
			}
			my_tlb = my_tlb->next;
		}
		//Found the 1 to replace
		memset(temp->tag,'\0',70);
		strcpy(temp->tag,address);
		if (i == TLB_INSTR) temp->val = I_TLB_VAL;
		else temp->val = D_TLB_VAL;
	}
	else if (my_tlb != NULL && D_TLB_COUNT == D_TLB_SIZE && i == TLB_DATA)
	{
		unsigned int t;
		int max = 0, tmp;
		if (i == TLB_INSTR) t = I_TLB_VAL;
		else t = D_TLB_VAL;
		tlb *temp = my_tlb;
		while (my_tlb != NULL)
		{
			tmp = diff(my_tlb->val,t);
			if (tmp > max )
			{
				temp = my_tlb;
				max = tmp;
			}
			my_tlb = my_tlb->next;
		}
		//Found the 1 to replace
		memset(temp->tag,'\0',70);
		strcpy(temp->tag,address);
		if (i == TLB_INSTR) temp->val = I_TLB_VAL;
		else temp->val = D_TLB_VAL;
	}
	else //cold miss: need to add one at the beginning
	{
		tlb *temp = (struct _tlb *) malloc(sizeof(struct _tlb));
		memset(temp->tag,'\0',70);
		strcpy(temp->tag, address);

		if (i == TLB_INSTR) temp->val = I_TLB_VAL;
		else temp->val = D_TLB_VAL;

		temp->next = my_tlb;
		temp->prev = NULL;
		if (my_tlb != NULL)
		{
			my_tlb->prev = temp;
		}
		my_tlb = temp;
		if (i == TLB_INSTR) first_itlb = my_tlb;
		else first_dtlb = my_tlb;
		if (TLB_INSTR == i) I_TLB_COUNT++;
		else D_TLB_COUNT++;
	}
}

void itlb_disp()
{
	tlb *my_tlb = first_itlb;
	printf("I TLB display\n");
	while (my_tlb != NULL)
	{
		printf("tag: %s ,",my_tlb->tag);
		printf("val: %d\n",my_tlb->val);
		my_tlb = my_tlb->next;
	}
}

void dtlb_disp()
{
	tlb *my_tlb = first_dtlb;
	printf("D TLB display\n");
	while (my_tlb != NULL)
	{
		printf("Tag: %s ,", my_tlb->tag);
		printf("val: %d\n", my_tlb->val);
		my_tlb = my_tlb->next;
	}
}

// I will use a doubly-linked queue for implementing LRU..
// If an element accessed is present in the queue, remove it and insert it at rear..
// Evict element always from front.. Add element always from rear..
// 0 - not present, 1 - present
cachedb* l1cache_search(char *address, int i)
{
	char *start = address;
	cachedb *my_cachedb = NULL;

	int l = 0;
	
	if (i == L1_INSTR)
	{
		char c_tag[64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET+1];
		memset(c_tag,'\0',64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET+1);
		address = start;
		for (l=0; l<(64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET); l++)
		{
			c_tag[l] = *address;
			address++;
		}

		char ind[L1_I_INDEXBITS+1];
		memset(ind,'\0',L1_I_INDEXBITS+1);
		//address = address+64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET;
		for (l=0; l<L1_I_INDEXBITS; l++)
		{
			ind[l] = *address;
			address++;
		}
		int index = bin2dec(ind);

		l1icache = l1icache_start;
		cacheset *temp = l1icache + (index * sizeof(struct _cacheset));
		if (temp->cdb != NULL)
		{
			cachedb *cdb_temp = temp->cdb;
			while (cdb_temp)
			{
				if (strcmp(cdb_temp->tag,c_tag) == 0)
				{
					my_cachedb = cdb_temp;
					break;
				}
				cdb_temp = cdb_temp->next;
			}
			
		}
	}
	else
	{
		char c_tag[64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET+1];
        	memset(c_tag,'\0',64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET+1);
        	address = start;
        	for (l=0; l<(64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET); l++)
        	{
                	c_tag[l] = *address;
                	address++;
        	}

        	char ind[L1_D_INDEXBITS+1];
       		memset(ind,'\0',L1_D_INDEXBITS+1);
        	//address = address+64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET;
        	for (l=0; l<L1_D_INDEXBITS; l++)
        	{
                	ind[l] = *address;
                	address++;
        	}
        	int index1 = bin2dec(ind);
               	l1dcache = l1dcache_start;
        	cacheset *temp = l1dcache + (index1 * sizeof(struct _cacheset));
        	if (temp->cdb != NULL)
        	{
                	cachedb *cdb_temp = (struct cache_db*)temp->cdb;
                	while (cdb_temp)
                	{
         	               	if (strcmp(cdb_temp->tag,c_tag) == 0)
               	        	{
                                	my_cachedb = cdb_temp;
                                	break;
                        	}
                        	cdb_temp = cdb_temp->next;
                	}
        	}
	}
	address = start;
	return my_cachedb;
}

int diff_cache(int m, int n, int which)
{
	int diff = n - m;
	if (diff < 0)
	{
		if (which == 1)
			diff = L1_I_CACHE_MAGICNO-m;
		else if (which == 2)
			diff = L1_D_CACHE_MAGICNO-m;
		else
			diff = L2_CACHE_MAGICNO-m;
		diff += n;
	}
	return diff;
}


//access -1 not present, 1 present
int l1cache_access(char *address, int i)
{
	cachedb *my_cachedb = l1cache_search(address, i);
	if (my_cachedb != NULL)
	{
		if (i == L1_INSTR)
		{
			I_L1_VAL = ++I_L1_VAL%L1_I_CACHE_MAGICNO;
			my_cachedb->val = I_L1_VAL;
		}
		else
		{
			D_L1_VAL = ++D_L1_VAL%L1_D_CACHE_MAGICNO;
			my_cachedb->val = D_L1_VAL;
		}
		
		return 1;
	}
	return -1;
}

void l1cache_miss(char *address, int i)
{
	char *start = address;
	if (i == L1_INSTR) 
	{
		I_L1_VAL = ++I_L1_VAL%L1_I_CACHE_MAGICNO;
	}
	else 
	{
		D_L1_VAL = ++D_L1_VAL%L1_D_CACHE_MAGICNO;
	}
	if (i == L1_INSTR)
        {
                char c_tag[64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET+1];
                memset(c_tag,'\0',64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET+1);
                address = start;
		int l;
                for (l=0; l<(64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET); l++)
                {
                        c_tag[l] = *address;
                        address++;
                }

                char ind[L1_I_INDEXBITS+1];
                memset(ind,'\0',L1_I_INDEXBITS+1);
                //address = address+64-L1_I_INDEXBITS-L1_I_BLOCKOFFSET;
                for (l=0; l<L1_I_INDEXBITS; l++)
                {
                        ind[l] = *address;
                        address++;
                }
                int index = bin2dec(ind);
                l1icache = l1icache_start;
                cacheset *temp = l1icache + (index * sizeof(struct _cacheset));
                if (temp->cdb != NULL)
                {
                        cachedb *cdb_temp = temp->cdb;
			int count = 1;
                        while (cdb_temp->next)
                        {
				count++;
                                cdb_temp = cdb_temp->next;
                        }
			if (count == L1ICACHE_ASSOCIATIVITY) // Need to evict one and add..
			{
				cdb_temp = temp->cdb;
				cachedb *cdb_temp1 = NULL;
				int max = 0, tmp;
				while (cdb_temp)
				{
					tmp = diff_cache(cdb_temp->val,I_L1_VAL,1);
					if (tmp > max)
					{
						max = tmp;
						cdb_temp1 = cdb_temp;
					}
					cdb_temp = cdb_temp->next;
				}
				strncpy(cdb_temp1->tag,c_tag,64);
				cdb_temp1->val = I_L1_VAL;
			}
			else
			{
				cachedb *cdb_temp1 = malloc(sizeof(struct cache_db));
	                        memset(cdb_temp1->tag,'\0',64);
       		                strncpy(cdb_temp1->tag,c_tag,64);
                        	cdb_temp1->val = I_L1_VAL;
                        	cdb_temp1->next = NULL;
                        	cdb_temp->next = cdb_temp1;
			}
                }
		else
		{
			cachedb *cdb_temp = malloc(sizeof(struct cache_db));
			memset(cdb_temp->tag,'\0',64);
			strncpy(cdb_temp->tag,c_tag,64);
			cdb_temp->val = I_L1_VAL;
			cdb_temp->next = NULL;
			temp->cdb = cdb_temp;
		}
        }
	else
	{
		char c_tag[64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET+1];
                memset(c_tag,'\0',64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET+1);
                address = start;
                int l;
                for (l=0; l<(64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET); l++)
                {
                        c_tag[l] = *address;
                        address++;
                }
                char ind[L1_D_INDEXBITS+1];
                memset(ind,'\0',L1_D_INDEXBITS+1);
                //address = address+64-L1_D_INDEXBITS-L1_D_BLOCKOFFSET;
                for (l=0; l<L1_D_INDEXBITS; l++)
                {
                        ind[l] = *address;
                        address++;
                }
                int index = bin2dec(ind);
                
                l1dcache = l1dcache_start;
                cacheset *temp = l1dcache + (index * sizeof(struct _cacheset));
		if (temp->cdb != NULL)
                {
                        cachedb *cdb_temp = temp->cdb;
                        int count = 1;
                        while (cdb_temp->next)
                        {
                                count++;
                                cdb_temp = cdb_temp->next;
                        }
                        if (count == L1DCACHE_ASSOCIATIVITY) // Need to evict one and add..
                        {
                                cdb_temp = temp->cdb;
                                cachedb *cdb_temp1 = NULL;
                                int max = 0, tmp;
                                while (cdb_temp)
                                {
                                        tmp = diff_cache(cdb_temp->val,D_L1_VAL,2);
                                        if (tmp > max)
                                        {
                                                max = tmp;
                                                cdb_temp1 = cdb_temp;
                                        }
                                        cdb_temp = cdb_temp->next;
                                }
                                strncpy(cdb_temp1->tag,c_tag,64);
                                cdb_temp1->val = D_L1_VAL;
                        }
                        else
                        {
                                cachedb *cdb_temp1 = malloc(sizeof(struct cache_db));
                                memset(cdb_temp1->tag,'\0',64);
                                strncpy(cdb_temp1->tag,c_tag,64);
                                cdb_temp1->val = D_L1_VAL;
                                cdb_temp1->next = NULL;
                                cdb_temp->next = cdb_temp1;
                        }
                      
                }
		else
                {
                        cachedb *cdb_temp = malloc(sizeof(struct cache_db));
                        memset(cdb_temp->tag,'\0',64);
                        strncpy(cdb_temp->tag,c_tag,64);
                        cdb_temp->val = I_L1_VAL;
                        cdb_temp->next = NULL;
                        temp->cdb = cdb_temp;
                }
		address = start;
	}
}

cachedb* l2cache_search(char *address)
{
	char *start = address;
	cachedb *my_cachedb = NULL;

	int l = 0;
	char c_tag[64-L2_INDEXBITS-L2_BLOCKOFFSET+1];
	memset(c_tag,'\0',64-L2_INDEXBITS-L2_BLOCKOFFSET+1);
	address = start;
	for (l=0; l<(64-L2_INDEXBITS-L2_BLOCKOFFSET); l++)
	{
		c_tag[l] = *address;
		address++;
	}

	char ind[L2_INDEXBITS+1];
	memset(ind,'\0',L2_INDEXBITS+1);
	//address = address+64-L2_INDEXBITS-L2_BLOCKOFFSET;
	for (l=0; l<L2_INDEXBITS; l++)
	{
		ind[l] = *address;
		address++;
	}
	int index = bin2dec(ind);

	l2cache = l2cache_start;
	cacheset *temp = l2cache + (index * sizeof(struct _cacheset));
	if (temp->cdb != NULL)
	{
		cachedb *cdb_temp = temp->cdb;
		while (cdb_temp)
		{
			if (strcmp(cdb_temp->tag,c_tag) == 0)
			{
				my_cachedb = cdb_temp;
				break;
			}
			cdb_temp = cdb_temp->next;
		}
	}
	
	address = start;
	return my_cachedb;
}


int l2cache_access(char *address)
{
	cachedb *my_cachedb = l2cache_search(address);
	if (my_cachedb != NULL)
	{
		L2_VAL = ++L2_VAL%L2_CACHE_MAGICNO;
		my_cachedb->val = L2_VAL;
		return 1;
	}
	return -1;
}

void l2cache_miss(char *address)
{
	char *start = address;
	L2_VAL = ++L2_VAL%L2_CACHE_MAGICNO;
        char c_tag[64-L2_INDEXBITS-L2_BLOCKOFFSET+1];
        memset(c_tag,'\0',64-L2_INDEXBITS-L2_BLOCKOFFSET+1);
        address = start;
	int l;
        for (l=0; l<(64-L2_INDEXBITS-L2_BLOCKOFFSET); l++)
        {
        	c_tag[l] = *address;
                address++;
        }
        
        char ind[L2_INDEXBITS+1];
        memset(ind,'\0',L2_INDEXBITS+1);
        //address = address+64-L2_INDEXBITS-L2_BLOCKOFFSET;
        for (l=0; l<L2_INDEXBITS; l++)
        {
        	ind[l] = *address;
                address++;
        }
        int index = bin2dec(ind);
        
        l2cache = l2cache_start;
        cacheset *temp = l2cache + (index * sizeof(struct _cacheset));
        if (temp->cdb != NULL)
        {
        	cachedb *cdb_temp = temp->cdb;
		int count = 1;
                while (cdb_temp->next)
                {
			count++;
                        cdb_temp = cdb_temp->next;
                }
		if (count == L2CACHE_ASSOCIATIVITY) // Need to evict one and add..
		{
			cdb_temp = temp->cdb;
			cachedb *cdb_temp1 = NULL;
			int max = 0, tmp;
			while (cdb_temp)
			{
				tmp = diff_cache(cdb_temp->val,L2_VAL,2);
				if (tmp > max)
				{
					max = tmp;
					cdb_temp1 = cdb_temp;
				}
				cdb_temp = cdb_temp->next;
			}
			strncpy(cdb_temp1->tag,c_tag,64);
			cdb_temp1->val = L2_VAL;
			// Cache Change starts- Nikhil
			cachedb *my_cachedb_l1_inst = l1cache_search(start, L1_INSTR);
			if (my_cachedb_l1_inst != NULL)
			{
				cdb_temp1 = NULL;
				
			}
			cachedb *my_cachedb_l1_data = l1cache_search(start, L1_DATA);
			if (my_cachedb_l1_data != NULL)
			{
				cdb_temp1 = NULL;
			}
			// Cache change ends
		}
		else
		{
			cachedb *cdb_temp1 = malloc(sizeof(struct cache_db));
	                memset(cdb_temp1->tag,'\0',64);
       	                strncpy(cdb_temp1->tag,c_tag,64);
                       	cdb_temp1->val = L2_VAL;
                       	cdb_temp1->next = NULL;
                       	cdb_temp->next = cdb_temp1;
		}
        }
	else
	{
		cachedb *cdb_temp = malloc(sizeof(struct cache_db));
		memset(cdb_temp->tag,'\0',64);
		strncpy(cdb_temp->tag,c_tag,64);
		cdb_temp->val = L2_VAL;
		cdb_temp->next = NULL;
		temp->cdb = cdb_temp;
	}
}

void l1cache_i_disp()
{
	printf("I Cache disp\n");
	l1icache = l1icache_start;
	cacheset *temp;
	int i;
	for (i=0; i<NO_OF_SETS_L1_I; i++)
	{
		temp = (struct _cacheset *) l1icache;
		if (temp->cdb != NULL)
		{
			cachedb *cdb_temp = temp->cdb;
			while (cdb_temp)
			{
				printf("Tag: %s, Val : %d\n",cdb_temp->tag, cdb_temp->val);
				cdb_temp = cdb_temp->next;
			}
		}
		l1icache += sizeof(struct _cacheset);
	}
}

void l1cache_d_disp()
{
	printf("D Cache disp\n");
        l1dcache = l1dcache_start;
        cacheset *temp;
        int i;
        for (i=0; i<NO_OF_SETS_L1_D; i++)
        {
                temp = (struct _cacheset *) l1dcache;
                if (temp->cdb != NULL)
                {
                        cachedb *cdb_temp = temp->cdb;
                        while (cdb_temp)
                        {
                                printf("Tag: %s, Val : %d\n",cdb_temp->tag, cdb_temp->val);
                                cdb_temp = cdb_temp->next;
                        }
                }
                l1dcache += sizeof(struct _cacheset);
        }
}

void l2cache_disp()
{
	printf("L2 Cache disp\n");
        l2cache = l2cache_start;
        cacheset *temp;
        int i;
        for (i=0; i<NO_OF_SETS_L2; i++)
        {
                temp = (struct _cacheset *) l2cache;
                if (temp->cdb != NULL)
                {
                        cachedb *cdb_temp = temp->cdb;
                        while (cdb_temp)
                        {
                                printf("Tag: %s, Val : %d\n",cdb_temp->tag, cdb_temp->val);
                                cdb_temp = cdb_temp->next;
                        }
                }
                l2cache += sizeof(struct _cacheset);
        }
}
